package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         85,
		Discription: "矩阵中数字为1的最大矩形",
		Level:       3,
		Labels: map[string]int{
			"栈":   1,
			"单调栈": 1,
			"矩阵":  1,
		},
	})
}

func MaximalRectangle(matrix [][]byte) int {
	m := len(matrix)
	n := len(matrix[0])
	//leftLength[i][j]表示（i，j）处自身以及左边最长连续1的个数
	leftLens := make([][]int, m)
	for i := 0; i < m; i++ {
		leftLens[i] = make([]int, n)
	}

	leftLens[0][0] = int(matrix[0][0] - '0')
	maxArea := leftLens[0][0]
	for i := 1; i < m; i++ {
		if matrix[i][0] == '1' {
			leftLens[i][0] = 1
			maxArea = 1
		}
	}

	//初始化第一列的leftLens
	for j := 1; j < n; j++ {
		for i := 0; i < m; i++ {
			if matrix[i][j] == '0' {
				leftLens[i][j] = 0
			} else {
				leftLens[i][j] = leftLens[i][j-1] + 1
			}
		}
	}

	//遍历每一列，转化为上一题求柱状图中最大矩阵面积的问题
	//必须从0开始
	for j := 0; j < n; j++ {
		s := []int{-1}
		tempArea := 0
		for i := 0; i < m; i++ {
			for len(s) > 1 && leftLens[s[len(s)-1]][j] >= leftLens[i][j] {
				h := leftLens[s[len(s)-1]][j]
				s = s[:len(s)-1]
				w := i - s[len(s)-1] - 1
				tempArea = max(tempArea, w*h)
			}
			s = append(s, i)
		}

		for len(s) > 1 {
			h := leftLens[s[len(s)-1]][j]
			s = s[:len(s)-1]
			w := m - 1 - s[len(s)-1]
			tempArea = max(tempArea, w*h)
		}

		maxArea = max(tempArea, maxArea)
	}

	return maxArea
}
